home *** CD-ROM | disk | FTP | other *** search
/ EnigmA Amiga Run 1995 October / EnigmA AMIGA RUN 01 (1995)(G.R. Edizioni)(IT)[!][issue 1995-10][Aminet 7].iso / Aminet / dev / gcc / ixemul_src.lha / ixemul-41.0 / network / insert.c < prev    next >
C/C++ Source or Header  |  1995-05-18  |  8KB  |  313 lines
  1. /*-
  2.  * Copyright (c) 1990 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Mike Olson.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)insert.c    5.3 (Berkeley) 2/22/91";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. #include <sys/types.h>
  42. #include <db.h>
  43. #include <stdlib.h>
  44. #include <string.h>
  45. #include "btree.h"
  46.  
  47. /*
  48.  *  _BT_INSERT -- Insert a new user datum in the btree.
  49.  *
  50.  *    This routine is called by bt_put, the public interface, once the
  51.  *    location for the new item is known.  We do the work here, and
  52.  *    handle splits if necessary.
  53.  *
  54.  *    Parameters:
  55.  *        t -- btree in which to do the insertion.
  56.  *        item -- BTITEM describing location of new datum
  57.  *        key -- key to insert
  58.  *        data -- data associated with key
  59.  *        flag -- magic cookie passed recursively to bt_put if we
  60.  *            have to do a split
  61.  *
  62.  *    Returns:
  63.  *        RET_SUCCESS, RET_ERROR.
  64.  */
  65.  
  66. int
  67. _bt_insert(t, item, key, data, flag)
  68.     BTREE_P t;
  69.     BTITEM *item;
  70.     DBT *key;
  71.     DBT *data;
  72.     int flag;
  73. {
  74.     index_t index;
  75.     BTHEADER *h;
  76.     DATUM *d;
  77.     int nbytes;
  78.     int status;
  79.     pgno_t pgno;
  80.     int keysize, datasize;
  81.     int bigkey, bigdata;
  82.  
  83.     if (_bt_getpage(t, item->bti_pgno) == RET_ERROR)
  84.         return (RET_ERROR);
  85.     h = t->bt_curpage;
  86.  
  87.     if (TOOBIG(t, data->size)) {
  88.         bigdata = TRUE;
  89.         datasize = sizeof(pgno_t);
  90.     } else {
  91.         bigdata = FALSE;
  92.         datasize = data->size;
  93.     }
  94.  
  95.     if (TOOBIG(t, key->size)) {
  96.         bigkey = TRUE;
  97.         keysize = sizeof(pgno_t);
  98.     } else {
  99.         bigkey = FALSE;
  100.         keysize = key->size;
  101.     }
  102.  
  103.     nbytes = keysize + datasize + (sizeof(DATUM) - sizeof(char));
  104.     nbytes = LONGALIGN(nbytes) + sizeof(index_t);
  105.  
  106.     /* if there's not enough room here, split the page */
  107.     if ((h->h_upper - h->h_lower) < nbytes) {
  108.         if (_bt_split(t) == RET_ERROR)
  109.             return (RET_ERROR);
  110.  
  111.         /* okay, try again (empty the stack first, though) */
  112.         while (_bt_pop((BTREE) t) != P_NONE)
  113.             continue;
  114.  
  115.         return (bt_put((BTREE) t, key, data, flag));
  116.     }
  117.  
  118.     /* put together a leaf page datum from the key/data pair */
  119.     index = item->bti_index;
  120.     nbytes = keysize + datasize + (sizeof(DATUM) - sizeof(char));
  121.  
  122.     if ((d = (DATUM *) malloc((unsigned) nbytes)) == (DATUM *) NULL)
  123.         return (RET_ERROR);
  124.  
  125.     d->d_ksize = keysize;
  126.     d->d_dsize = datasize;
  127.     d->d_flags = 0;
  128.  
  129.     if (bigkey) {
  130.         if (_bt_indirect(t, key, &pgno) == RET_ERROR)
  131.             return (RET_ERROR);
  132.         (void) bcopy((char *) &pgno, &(d->d_bytes[0]), sizeof(pgno));
  133.         d->d_flags |= D_BIGKEY;
  134.         if (_bt_getpage(t, item->bti_pgno) == RET_ERROR)
  135.             return (RET_ERROR);
  136.     } else {
  137.         if (d->d_ksize > 0) {
  138.             (void) bcopy((char *) key->data,
  139.                       (char *) &(d->d_bytes[0]),
  140.                       (int) d->d_ksize);
  141.         }
  142.     }
  143.  
  144.     if (bigdata) {
  145.         if (_bt_indirect(t, data, &pgno) == RET_ERROR)
  146.             return (RET_ERROR);
  147.         (void) bcopy((char *) &pgno,
  148.                  &(d->d_bytes[keysize]),
  149.                  sizeof(pgno));
  150.         d->d_flags |= D_BIGDATA;
  151.         if (_bt_getpage(t, item->bti_pgno) == RET_ERROR)
  152.             return (RET_ERROR);
  153.     } else {
  154.         if (d->d_dsize > 0) {
  155.             (void) bcopy((char *) data->data,
  156.                       (char *) &(d->d_bytes[keysize]),
  157.                       (int) d->d_dsize);
  158.         }
  159.     }
  160.  
  161.     /* do the insertion */
  162.     status = _bt_insertat(t, (char *) d, index);
  163.  
  164.     (void) free((char *) d);
  165.  
  166.     return (status);
  167. }
  168.  
  169. /*
  170.  *  _BT_INSERTI -- Insert IDATUM on current page in the btree.
  171.  *
  172.  *    This routine handles insertions to internal pages after splits
  173.  *    lower in the tree.  On entry, t->bt_curpage is the page to get
  174.  *    the new IDATUM.  We are also given pgno, the page number of the
  175.  *    IDATUM that is immediately left of the new IDATUM's position.
  176.  *    This guarantees that the IDATUM for the right half of the page
  177.  *    after a split goes next to the IDATUM for its left half.
  178.  *
  179.  *    Parameters:
  180.  *        t -- tree in which to do insertion.
  181.  *        id -- new IDATUM to insert
  182.  *        pgno -- page number of IDATUM left of id's position
  183.  *
  184.  *    Returns:
  185.  *        RET_SUCCESS, RET_ERROR.
  186.  */
  187.  
  188. int
  189. _bt_inserti(t, id, pgno)
  190.     BTREE_P t;
  191.     IDATUM *id;
  192.     pgno_t pgno;
  193. {
  194.     BTHEADER *h = t->bt_curpage;
  195.     index_t next, i;
  196.     IDATUM *idx;
  197.     char *key;
  198.     pgno_t chain;
  199.     int free_key;
  200.     int ignore;
  201.  
  202.     if (id->i_flags & D_BIGKEY) {
  203.         free_key = TRUE;
  204.         bcopy(&(id->i_bytes[0]), (char *) &chain, sizeof(chain));
  205.         if (_bt_getbig(t, chain, &key, &ignore) == RET_ERROR)
  206.             return (RET_ERROR);
  207.     } else {
  208.         free_key = FALSE;
  209.         key = &(id->i_bytes[0]);
  210.     }
  211.     i = _bt_binsrch(t, key);
  212.  
  213.     next = NEXTINDEX(h);
  214.     while (i < next && _bt_cmp(t, key, i) >= 0)
  215.         i++;
  216.  
  217.     if (free_key)
  218.         (void) free(key);
  219.  
  220.     /* okay, now we're close; find adjacent IDATUM */
  221.     for (;;) {
  222.         idx = (IDATUM *) GETDATUM(h,i);
  223.         if (idx->i_pgno == pgno) {
  224.             i++;
  225.             break;
  226.         }
  227.         --i;
  228.     }
  229.  
  230.     /* correctly positioned, do the insertion */
  231.     return (_bt_insertat(t, (char *) id, i));
  232. }
  233.  
  234. /*
  235.  *  _BT_INSERTAT -- Insert a datum at a given location on the current page.
  236.  *
  237.  *    This routine does insertions on both leaf and internal pages.
  238.  *
  239.  *    Parameters:
  240.  *        t -- tree in which to do insertion.
  241.  *        p -- DATUM or IDATUM to insert.
  242.  *        index -- index in line pointer array to put this item.
  243.  *
  244.  *    Returns:
  245.  *        RET_SUCCESS, RET_ERROR.
  246.  *
  247.  *    Side Effects:
  248.  *        Will rearrange line pointers to make space for the new
  249.  *        entry.  This means that any scans currently active are
  250.  *        invalid after this.
  251.  *
  252.  *    Warnings:
  253.  *        There must be sufficient room for the new item on the page.
  254.  */
  255.  
  256. int
  257. _bt_insertat(t, p, index)
  258.     BTREE_P t;
  259.     char *p;
  260.     index_t index;
  261. {
  262.     IDATUM *id = (IDATUM *) p;
  263.     DATUM *d = (DATUM *) p;
  264.     BTHEADER *h;
  265.     CURSOR *c;
  266.     index_t nxtindex;
  267.     char *src, *dest;
  268.     int nbytes;
  269.  
  270.     /* insertion may confuse an active scan.  fix it. */
  271.     c = &(t->bt_cursor);
  272.     if (t->bt_flags & BTF_SEQINIT && t->bt_curpage->h_pgno == c->c_pgno)
  273.         if (_bt_fixscan(t, index, d, INSERT) == RET_ERROR)
  274.             return (RET_ERROR);
  275.  
  276.     h = t->bt_curpage;
  277.     nxtindex = (index_t) NEXTINDEX(h);
  278.  
  279.     /*
  280.      *  If we're inserting at the middle of the line pointer array,
  281.      *  copy pointers that will follow the new one up on the page.
  282.      */
  283.  
  284.     if (index < nxtindex) {
  285.         src = (char *) &(h->h_linp[index]);
  286.         dest = (char *) &(h->h_linp[index + 1]);
  287.         nbytes = (h->h_lower - (src - ((char *) h)))
  288.              + sizeof(h->h_linp[0]);
  289.         (void) bcopy(src, dest, nbytes);
  290.     }
  291.  
  292.     /* compute size and copy data to page */
  293.     if (h->h_flags & F_LEAF) {
  294.         nbytes = d->d_ksize + d->d_dsize
  295.              + (sizeof(DATUM) - sizeof(char));
  296.     } else {
  297.         nbytes = id->i_size + (sizeof(IDATUM) - sizeof(char));
  298.     }
  299.     dest = (((char *) h) + h->h_upper) - LONGALIGN(nbytes);
  300.     (void) bcopy((char *) p, dest, nbytes);
  301.  
  302.     /* update statistics */
  303.     dest -= (int) h;
  304.     h->h_linp[index] = (index_t) dest;
  305.     h->h_upper = (index_t) dest;
  306.     h->h_lower += sizeof(index_t);
  307.  
  308.     /* we're done */
  309.     h->h_flags |= F_DIRTY;
  310.  
  311.     return (RET_SUCCESS);
  312. }
  313.